package com.ting.test.algorithms.并查集.岛问题;

import java.util.ArrayList;
import java.util.List;

/**
 * 岛问题扩展
 * <p>
 * 给定一个m*n的二维数组matrix，初始状态下 数组内的元素都是0，
 * <p>
 * 每次动态的给出一组坐标，坐标代表的元素的位置将被置为1
 * 且上、下、左、右相邻的1认为是一片岛，
 * 返回每一次添加新的坐标位置后，matrix中岛的数量
 * 思路
 * 利用并查集的方法，每次在接收一个新的坐标时，动态的初始化该坐标的相关信息
 * 同时判断该坐的上下左右坐标是否是1，是则关联
 */
public class 岛问题扩展 {
    public static void main(String[] args) {
//        int[][] arr = new int[][]{{1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0}, {1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0}, {1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0}};
        int[][] arr = new int[][]{{1, 1}, {1, 0}, {1, 2}};
        UnionFind uf = new UnionFind(10, 10);

        //一个一个动态的添加元素
        List<Integer> countList = new ArrayList<>();
        for (int[] position : arr) {
            countList.add(uf.connect(position[0], position[1]));
        }
    }


    static class UnionFind {
        int[] parent;//表示元素的父节点的下标
        int[] help;//辅助
        int[] size;//size[i]=x 表示下标为i的元素所在的集合的元素个数 i为该集合的代表元素
        int sets = 0;//当前的集合数
        int row;
        int col;


        public UnionFind(int row, int col) {
            parent = new int[row * col];
            this.size = new int[row * col];
            this.row = row;
            this.col = col;

        }


        /**
         * 查找当前元素对应的父元素
         * 在查找的过程中，将从index元素到代表元素之间的所有元素的父元素都设置为代表元素
         * 当parent方法被调用足够多次数的时候，该方法的时间复杂度近似于O(1)
         *
         * @return
         */
        public int parent(int index) {
            help = new int[parent.length];
            int i = 0;
            while (parent[index] != index) {
                help[i++] = index;
                index = parent[index];
            }
            while (i > 0) {
                help[i--] = index;
            }
            return index;

        }


        public int connect(int r, int c) {
            int index = index(r, c);
            //动态初始化元素
            if (size[index] == 0) {//默认情况下，size[index]==0，当index被初始化一次后，该位置将不再变为0，因此可以通过次位置判断index是否已被初始
                parent[index] = index;//初始
                size[index] = 1;
                sets++;
                //依次感染上下左右的元素 注意这个方法不是递归
                union(r - 1, c, r, c);
                union(r + 1, c, r, c);
                union(r, c - 1, r, c);
                union(r, c + 1, r, c);
            }
            return sets;

        }

        private void union(int r1, int c1, int r2, int c2) {
            if (r1 < 0 || r1 >= row || r2 < 0 || r2 >= row || c1 < 0 || c1 >= col || c2 < 0 || c2 >= col) {
                return;
            }

            int n1 = index(r1, c1);
            int n2 = index(r2, c2);

            if (size[n1] == 0 || size[n2] == 0) {//==0表示该坐标未初始化，不需要合并
                return;
            }

            int p1 = parent(n1);
            int p2 = parent(n2);
            if (p1 == p2) {
                return;
            }

            int s1 = size[p1];
            int s2 = size[p2];
            sets--;
            //此处不处理较小的那个集合的size个数，保证初始化过的size一定是大于0的
            if (s1 > s2) {
                parent[p2] = p1;
                size[p1] = s1 + s2;
            } else {
                parent[p1] = p2;
                size[p2] = s1 + s2;
            }
        }


        /**
         * 将二维数组转换为一维数组的坐标
         *
         * @param i
         * @param j
         * @return
         */
        public int index(int i, int j) {
            return i * col + j;
        }
    }

}

